package leetcode.code1545;

public class Solution {
	public char findKthBit(int n, int k) {
		return this.f(n, k, true);
	}

	private char f(int n, int k, boolean b) {
		int mid = (int) Math.pow(2, n - 1);
		if (k == mid) {
			return b ? n == 1 ? '0' : '1' :  n == 1 ? '1' : '0';
		}
		if (k < mid) {
			return this.f(n - 1, k, b);
		} else {
			return this.f(n - 1, (mid << 1) - k, !b);
		}
	}
}
